/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.search;

import java.util.ArrayList;
import java.util.List;

import kaist.sep502.tsp.model.City;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.model.Solution;

/**
 * @author minho kim
 * 
 */
public class ApproximatedSolution extends SearchAlgorithm {

	/** */
	private static final int $$_DEB_55 = -55;

	/**
	 * @param problem
	 */
	public ApproximatedSolution(Problem problem) {
		super(problem);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see kaist.sep502.tsp.algorithm.search.SearchAlgorithm#search()
	 */
	@Override
	public Solution search() {

		solution = new Solution("Approximated Solution");
		solution.startStopWatch();
		solution.expandedNodeCount = 0;

		double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE, maxX = 0.0, maxY = 0.0;
		// i : cityNo가 아님.
		for (int i = 0; i < problem.citySize; i++) {
			City city = problem.getCity(i);
			double x = city.getX(), y = city.getY();
			if (x < minX) {
				minX = x;
			}

			if (x > maxX) {
				maxX = x;
			}

			if (y < minY) {
				minY = y;
			}

			if (y > maxY) {
				maxY = y;
			}
		}

		// TODO 구획을 나누는 알고리즘.
		int areaSize = 10;
		int xAreaSize = 5;
		List<Area> areaList = new ArrayList<Area>(areaSize);

		// Area 초기화.
		double I = 0.0;
		for (int i = 1; i <= areaSize; i++) {
			Area area = new Area();
			I = (double) i;
			area.x = (I / xAreaSize) <= 1 ? maxX * ((I - 1) / xAreaSize) : maxX
					* ((areaSize - I) / xAreaSize);
			area.y = (I / xAreaSize) <= 1 ? minY : maxY / 2;
			area.w = (I / xAreaSize) <= 1 ? maxX * (I / xAreaSize) : maxX
					* ((areaSize - I + 1) / xAreaSize);
			area.h = (I / xAreaSize) <= 1 ? maxY / 2 : maxY;

			areaList.add(area);
		}

		// Area에 City를 분할해서 넣기.
		for (int i = 0; i < problem.citySize; i++) {
			City city = problem.getCity(i);
			for (int j = 0; j < areaSize; j++) {
				Area area = areaList.get(j);
				double x = city.getX(), y = city.getY();
				if (area.x <= x && x <= area.w && area.y <= y && y <= area.h) {
					area.cityList.add(city);
					area.firstCityNo = -99; // 임시로 저장.
					area.lastCityNo = -99; // 임시로 저장.
				}
			}
		}

		// City 항목이 없는 영역은 삭제한다.
		for (int i = 0; i < areaList.size(); i++) {
			if (areaList.get(i).cityList.size() == 0) {
				areaList.remove(i--);
			}
		}
		areaSize = areaList.size();

		// 빠진 것이 없는지 검증.
		// PriorityQueue<Integer> cityList = new PriorityQueue<Integer>();
		// for(int i=0; i < areaSize; i++){
		// Area area = areaList.get(i);
		// Iterator iter = area.cityMap.keySet().iterator();
		// while(iter.hasNext()){
		// cityList.add(new Integer(area.cityMap.get(iter.next()).getCityNo()));
		// }
		// }
		//
		// while(cityList.isEmpty() != true){
		// System.out.print(cityList.poll());
		// System.out.print(",");
		// }

		// 각 영역의 연결점 찾기.
		Area area1, area2;
		City city1, city2;
		for (int k = 1; k <= areaSize; k++) {
			if (k == areaSize) {
				area1 = areaList.get(k - 1);
				area2 = areaList.get(0);
			} else {
				area1 = areaList.get(k - 1);
				area2 = areaList.get(k);
			}
			double minDistance = Double.MAX_VALUE;
			int cityNo1 = $$_DEB_55;
			int cityNo2 = $$_DEB_55;
			for (int i = 0; i < area1.cityList.size(); i++) {
				for (int j = 0; j < area2.cityList.size(); j++) {
					city1 = area1.cityList.get(i);
					city2 = area2.cityList.get(j);
					if (area1.cityList.size() > 1) {
						if (city1.getCityNo() == area1.firstCityNo
								|| city1.getCityNo() == area1.lastCityNo
								|| city2.getCityNo() == area2.firstCityNo
								|| city2.getCityNo() == area2.lastCityNo) {
							continue;
						}
					}
					try {
						double distance = problem.calculateDistance(city1, city2);
						if (distance < minDistance) {
							minDistance = distance;
							cityNo1 = area1.cityList.get(i).getCityNo();
							cityNo2 = area2.cityList.get(j).getCityNo();
						}
					} catch (Exception e) {
						e.printStackTrace();
					}
				}
			}
			area1.lastCityNo = cityNo1;
			area2.firstCityNo = cityNo2;

			if (area1.lastCityNo == $$_DEB_55) {
				switch (area1.cityList.size()) {
				case 1:
					area1.lastCityNo = area1.cityList.get(0).getCityNo();
					break;
				case 2:
					area1.lastCityNo = (area1.firstCityNo == area1.cityList.get(0).getCityNo()) ? area1.cityList
							.get(1).getCityNo() : area1.cityList.get(0).getCityNo();
					break;
				default:
					break;
				}
			}

			if (area2.firstCityNo == $$_DEB_55) {
				switch (area2.cityList.size()) {
				case 1:
					area2.firstCityNo = area2.cityList.get(0).getCityNo();
					break;
				case 2:
					area2.firstCityNo = (area2.lastCityNo == area2.cityList.get(0).getCityNo()) ? area2.cityList
							.get(1).getCityNo() : area2.cityList.get(0).getCityNo();
					break;
				default:
					break;
				}
			}
		}

		// 각 영역 별로 Problem, Solution 초기화.
		for (int i = 0; i < areaSize; i++) {
			Area area = areaList.get(i);
			area.problem = new Problem();
			// 목적 city를 원점으로 하면 시작/끝점 중심의 최적의 경로를 구할 수 없다.
			try {
				area.problem.init(area.cityList, area.firstCityNo, area.lastCityNo);
			} catch (Exception e) {
				e.printStackTrace();
			}
			area.solution = new Solution("Approximated Solution");

//			System.out.println("A" + i + " nodes : " + area.cityList.size());
		}

		// 각 영역 별로 IDS로 최단 거리 구하기.
		for (int i = 0; i < areaSize; i++) {
			Area area = areaList.get(i);
			int areaCitySize = area.cityList.size();
			if(areaCitySize == 1){
				area.solution.goalCityPath = new CityPath(area.problem, area.firstCityNo);
				area.solution.setSuccess(true);
			} else if (areaCitySize == 2){
				area.solution.goalCityPath = new CityPath(area.problem, area.firstCityNo);
				try {
					area.solution.goalCityPath.moveTo(area.problem, area.lastCityNo, 0.0);
				} catch (Exception e) {
					e.printStackTrace();
				}
			} else if (2 < areaCitySize && areaCitySize <= 12){
				IterativeDeepeningSearch ids = new IterativeDeepeningSearch(area.problem);
				area.solution = ids.search();
			} else if (14 < areaCitySize && areaCitySize <= 20){
				SearchAlgorithm sa = new IdsAndAStarSearch(area.problem);
				area.solution = sa.search();
			} else {
				 SearchAlgorithm sa = new AStarSearch(area.problem);
				 area.solution = sa.search();
			}

		}

		// 전체를 하나의 경로 만들기.
		CityPath path = new CityPath(problem, areaList.get(0).firstCityNo);
		try {
			for (int i = 0; i < areaSize; i++) {
				Area area = areaList.get(i);

				// j는 cityNo가 아님.
				int tempCityNo;
				for (int j = 0; j < area.solution.goalCityPath.tourHistory.size(); j++) {
					tempCityNo = area.solution.goalCityPath.tourHistory.get(j);
					if (path.tourHistory.contains(tempCityNo)) {
						continue;
					} else {

						path.moveTo(problem, tempCityNo, 0.0);

					}
				}
				solution.expandedNodeCount += area.solution.expandedNodeCount;
			}
			path.moveTo(problem, path.tourHistory.get(0), 0.0); // 마지막 연결을 한다.
		} catch (Exception e) {
			e.printStackTrace();
		}

		solution.goalCityPath = path;
		solution.setSuccess(true);
		solution.stopStopWatch();
		return solution;
	}
}

class Area {
	List<City> cityList = new ArrayList<City>();
	double x, y, w, h;
	Solution solution;
	Problem problem;
	int firstCityNo;
	int lastCityNo;
}
